A common problem in database technology is to ensure short response times to database queries which require processing large volumes of data. For example, such computing-power consuming processing has to be performed in response to so-called “open queries” which contain only little input information (e.g. only one or two parameters out of a dozen possible parameters are specified and/or the specified value ranges of the parameters are broad) and, consequently, lead to a large number of results in general. Possibilities to speed up data processing by increasing hardware performance are limited. Thus, attention is drawn to improving the mechanisms underlying the processing of large data volumes.
One general approach to shorten query times is to pre-compute expected queries and to maintain the corresponding query results in a cache system. Queries are then actually not processed on the large data basis, but are directed to the cache system.
Another issue, however, which comes along with such caching approaches, is to keep the pre-computed query results up-to-date in order to ensure that queries responded by the cached results correctly reflect the status of the corresponding large data basis. In case the underlying data changes, the cached query results get outdated and the cache system would return incorrect results. Thus, strategies are needed how the cache system can be kept up-to-date.
Various relatively simple update strategies are known in the prior art like, for example, re-computing the entire data domain frequently, establishing and maintaining re-computation schedules manually and re-computing data when they are getting too old.
Somewhat more sophisticated update strategies have been developed, as e.g., described by WO 01/33472 and WO 02/25557.
WO 01/33472 concerns an availability system used in a travel planning system. The system includes a cache having entries of availability information regarding airline seats. A cache manager manages entry information in the cache in order to keep information in the cache correct, current, complete or otherwise as useful as possible. In response to a query directed to the cache, the cache manager determines if a stored answer is stale and, if this is the case, sends an availability query to a source of availability information. Cache entries to be modified are obtained by asynchronous notifications from external systems and determined by a deterministic, predictive or statistical model.
Similarly, WO 02/25557 pertains to an information retrieval system wherein information received from information sources is cached for future use, such as for future client requests. Proactive queries can be generated to populate a cache and/or to update presently cached information. In an airline information system, proactive queries are ordered on the basis of statistics or predictive indications such a nearness of departure time, the age of cached data, remaining seats in an aircraft, holidays or special events or equipment type. In addition, updates are received by external notifications from airlines such as AVS messages.